package zuo.algo.c07;

import zuo.algo.data.TreeNode;
import zuo.algo.util.TreeUtils;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 01:22-求二叉树两个节点的公共祖先节点
 * 给定两个二叉树的节点node1和node2，找到他们的最低公共祖先。
 */
public class LowestCommonAncestor {

    public static TreeNode lca1(TreeNode head, TreeNode node1, TreeNode node2) {
        Map<TreeNode, TreeNode> fatherMap = new HashMap<>();
        fatherMap.put(head, head);
        generateFatherMap(fatherMap, head);
        Set<TreeNode> fatherSetNode1 = new HashSet<>();
        TreeNode curr = node1;
        TreeNode fatherNode = fatherMap.get(curr);
        while (curr != fatherNode) {
            fatherSetNode1.add(curr);
            curr = fatherNode;
            fatherNode = fatherMap.get(curr);
        }
        fatherSetNode1.add(head);
        curr = node2;
        fatherNode = fatherMap.get(curr);
        while (curr != fatherNode) {
            if (fatherSetNode1.contains(curr)) {
                return curr;
            }
            curr = fatherNode;
            fatherNode = fatherMap.get(curr);
        }
        return head;
    }

    public static TreeNode lca2(TreeNode head, TreeNode node1, TreeNode node2) {
        return process(head, node1, node2);
    }

    private static TreeNode process(TreeNode node, TreeNode node1, TreeNode node2) {
        if (node == null || node == node1 || node == node2) {
            return node;
        }
        TreeNode left = process(node.left, node1, node2);
        TreeNode right = process(node.right, node1, node2);
        if (left != null && right != null) {
            return node;
        }
        return left != null ? left : right;
    }

    private static void generateFatherMap(Map<TreeNode, TreeNode> fatherMap, TreeNode node) {
        if (node.left != null) {
            fatherMap.put(node.left, node);
            generateFatherMap(fatherMap, node.left);
        }
        if (node.right != null) {
            fatherMap.put(node.right, node);
            generateFatherMap(fatherMap, node.right);
        }
    }

    public static void main(String[] args) {
        Map<Integer, TreeNode> map = new HashMap<>();
        TreeNode root = TreeUtils.getTree(map);
        TreeNode node1 = map.get(6);
        TreeNode node2 = map.get(8);
        TreeNode res1 = lca1(root, node1, node2);
        TreeNode res2 = lca2(root, node1, node2);
        if (res1 != res2) {
            System.out.println(res1.val + ":" + res2.val);
        }
        node1 = map.get(4);
        node2 = map.get(20);
        res1 = lca1(root, node1, node2);
        res2 = lca2(root, node1, node2);
        if (res1 != res2) {
            System.out.println(res1.val + ":" + res2.val);
        }
        node1 = map.get(14);
        node2 = map.get(20);
        res1 = lca1(root, node1, node2);
        res2 = lca2(root, node1, node2);
        if (res1 != res2) {
            System.out.println(res1.val + ":" + res2.val);
        }
    }
}
